package thired.class04_mergesort;

public class Class04_CountRangeSum {
    public static int countRangeSum(int[] nums,int lower, int upper){
        if(nums == null || nums.length == 0){
            return 0;
        }
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        return process(sum,0,nums.length-1,lower,upper);
    }

    public static int process(int[] sum,int l,int r,int lower, int upper){
        if(l==r){
            return sum[l] >= lower && sum[l] <= upper ? 1 : 0;
        }
        int m = l + ((r-l) >> 1 );

        return process(sum,l,m,lower,upper) +
                process(sum,m + 1,r,lower,upper)+
                merge(sum,l,m,r,lower,upper);
    }

    public static int merge(int[] sum,int l,int m,int r,int lower,int upper){
        int ans = 0;
        int windowL = l;
        int windowR = l;
        for (int i = m + 1; i <= r; i++) {
            int min = sum[i] - upper;
            int max = sum[i] - lower;
            while (windowR <= m && sum[windowR] <= max) {
                windowR++;
            }
            while (windowL <= m && sum[windowL] < min){
                windowL++;
            }
            ans += windowR - windowL;
        }

        int[] help = new int[r-l+1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while(p1 <= m && p2 <= r){
                help[i++] = sum[p1] <= sum[p2] ? sum[p1++] : sum[p2++];
        }
        while(p1 <= m){
            help[i++] = sum[p1++];
        }
        while (p2 <= r){
            help[i++] = sum[p2++];
        }
        for (int j = l; j <= r; j++) {
            sum[j] = help[j - l];
        }
        return ans;
    }
}
